import java.util.Scanner;

public class demo1 {
    public static void main(String[] args){
        int[] dp = new int[10001];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i < dp.length; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10000;
        }
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int num = scan.nextInt();
            int[] nums = new int[num];
            String password = "";
            for(int i = 0; i < nums.length; i++){
                nums[i] = scan.nextInt();
                String temp = dp[nums[i]] + 10000 + "";
                password += temp.substring(1,temp.length());
            }
            System.out.println(password);
        }
    }
}
